1. Field of the Invention
The present invention generally relates to general purpose digital data processing systems and more particularly relates to such systems which employ a priority scheme for allocating a shared resource between a number of independent users.
2. Description of the Prior Art
In most general purpose, stored program, digital computers, it is desirable to have shared resources contained therein. Each of the shared resources may be designed to service a number of users. Possible shared resources may include a bus, a memory, a processor, or any other element within the computer system. The concept of utilizing shared resources has been used for several years to decrease the number of components within a computer system thereby increasing the cost effectiveness of the system. The use of shared resources also reduces the overall size and power requirements of the computer system.
Although these benefits can be substantial, shared resources may reduce the band pass of a system if not carefully used and designed. One reason for this is that only one of the users may use the shared resource at any given time. That is, the users must "share" the resource. Consistent therewith, computer designers must weigh the advantage of using a shared resource against the band pass limiting effect inherent therein. To increase the number of applications for shared resources and thus to take advantage of the benefits attributable thereto, computer designers have attempted to increase the band pass of shared resource designs.
One method for increases the overall band pass of a shared resource design is to utilize priority schemes. For example, in a typical system, a number of processors may communicate with one another across a shared bi-directional bus. However, only one processors may use the shared bus at any given time. Therefore, the computer system must employ a mechanism for ensuring that only one processor has access to the shared bus at any given time while blocking access of the remaining processors. Often, one or more of the processors may have a greater need to access the shared bus. One reasons for this may be that one or more of the processors may be in the critical path of the computer system. If a processor is in the critical path of a computer system and it is not allowed to access the shared resource, the band pass of the entire computer system may suffer. A concrete example of this may be that a first of the processors connected to a shared bus may contain a memory therein for storing instructions which must be accessed by a main processor. A second of the processors connected to the shared bus may be responsible for controlling the IO ports connected to a printer. It is clear that the first processor should be given priority to use the shared bus over the second processor. If this is not the case, the "band pass" of the computer system may be reduced because the second processor may have control of the bus thereby prohibiting the main processor from fetching instructions from the first processor. This is just an example of where priority schemes are essential to proper operation of modern computer systems.
One scheme advanced for solving this problem is a pure "first-in-time" priority scheme. In a pure first-in-time priority scheme, each of the processors that are coupled to the shared bus may assert a bus request signal when the corresponding processor wants to use the shared bus. The first processor that asserts the corresponding bus request signal is given priority and control over the shared bus. If a second processor asserts it's corresponding bus request signal after the first processor has control over the bus, the second processor is denied access to the shared bus. After the first processor releases control of the bus, each processor is given another opportunity to obtain control of the bus by asserting it's corresponding bus request signal. This process is repeated during normal operation of the computer system.
It is evident that one or more of the processors coupled to the shared resource may be effectively blocked from using the shared resource for an extended period of time. If one of these processors is in the critical path of the computer system, the band pass of the computer system may suffer. In addition, all of the processors that are coupled to the shared resource are given an equal opportunity to access the shared resource every time the shared resource is released by a processor. That is, even the processor that previously had control of the shared resource has an equal opportunity to gain control of the shared resource during the next cycle. Because of the inherent disadvantages of the pure first-in-time scheme described hereinabove, only applications that are non-bandpass limited typically use the pure first-in-time scheme. However, in these applications, the pure first-in-time scheme has the advantage of being simple to implement thereby not requiring much overhead circuitry.
A modified first-in-time scheme has been developed to reduce some of the disadvantages inherent in the pure first-in-time scheme. The modified first-in-time scheme does not allow the processor that previously had control of the shared resource to gain control of the shared resource during the next succeeding bus cycle. This modification prohibits one processor from dominating a shared resource over an extended period of time. One disadvantage of the modified first-in-time scheme is that two or more processors may still dominate a shared resource thereby effectively blocking other processors from accessing the shared resource. For this to occur, however, the two or more processors must alternate in controlling the shared resource thereby giving access to at least two of the processors coupled thereto.
In some applications, it is important that each of the users that are coupled to a shared resource be given an opportunity to access the shared resource on a periodic basis. The modified first-in-time scheme may include circuitry to prohibit a user that previously had control of the shared resource to gain control of the shared resource during the next "N" succeeding bus cycles where N equals the number of users connected to the shared resource. In this configuration, the modified first-in-time scheme may allow all users access to the shared resource on a periodic basis.
Another priority scheme is termed the "first-in-place" scheme. The first-in-place scheme assigns a priority to each of the users connected to a shared resource. Each time an access to the shared resource is requested, the user having the highest priority assigned thereto is given access to the shared resource. For example, if a user having a priority of "2" and a user having a priority of "5" both request access to the shared resource, the first-in-place scheme will grant access to the user having the highest priority, namely the user having a priority of "2". Therefore, the users are assigned a priority value and are serviced in an order that is consistent with that value. Typically, the values assigned to the users are fixed and cannot be changed. A disadvantage of the first-in-place scheme is that the highest priority user may dominate the shared resource thereby effectively blocking access to lower priority users for extended periods of time.
One method for improving the first-in-place scheme is to rotate the assigned priority values among the users on a periodic basis. For example, a user having a priority value of "2" may be assigned a priority value of "1" and a user having a priority value of "3" may be assigned a priority value of "2". Therefore, each user is assigned a new priority value in a round robin fashion thus allowing access to the shared resource by all users on a periodic basis.
A similar approach is suggested in U.S. Pat. No. 5,195,185, issued on Mar. 16, 1993 to Marenin. Marenin suggests providing a separate processor which independently changes the priority values of all users. That is, Marenin suggests having the ability to change the priority value assigned to each user whenever the separate processor independently determines that it is necessary.
Although Marenin provides some additional flexibility to the first-in-place schemes, significant disadvantages still remain. First, the priority values of the users can only be changed at the direction of an independent processor which is not otherwise coupled to the users. Therefore, the separate processor must independently determine when a priority change should occur without regard to the current status of the users. Second, the separate processor can only load new priority values into the users at predetermined intervals. Between these intervals, the operation of the apparatus suggested in Marenin operates in the same manner as the first-in-place scheme described above.
A technique used to enhance the effectiveness of the above described priority schemes is known as the "snap-shot" technique. The snapshot technique captures the status of the resource requests signals provided by the users at a predetermined time. For example, at time T0 the resource request signal of a first user and a second user may be asserted while the resource request signal of a third user may not be asserted. If a "snap-shot" is taken at time T0, the values of the resource request signals at time T0 will be stored. If a first-in-place priority scheme is utilized, the users having an asserted captured resource request signal are serviced in the order of their assigned priority. In most systems employing the snap-shot technique, all of the users that have an asserted captured resource request signal are serviced in the order of their assigned priority before another snap-shot is taken. That is, users that did not have an asserted resource request signal when the previous snap-shot was taken are not allowed to access the shared resource until the next snap-shot is taken. Variations on this approach include time-shifting the snap-shot to favor one user over another.
Although the snap-shot technique may improve the effectiveness of some of the priority schemes described above, the snap-shot technique is limited by the inherent shortcomings of the underlying priority schemes.